/**
 * Minimum Window Substring
Given a string S and a string T, 
find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
 */
package com.xinpan.exercise;

public class MinWindowSubstring {
    public String minWindow(String S, String T) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[] hasF = new int[256];
        int[] needF = new int[256];
        
        for(int i = 0; i < 256; i++)
        {
            hasF[i] = 0;
        	needF[i] = 0;
        }
        
        for(int i = 0; i < T.length(); i++)
            needF[T.charAt(i)]++;
        
        int min = Integer.MAX_VALUE;
        String res = "";
        int count = 0;
        for(int s = 0, e = 0; e < S.length(); e++)
        {
            int ch = S.charAt(e);
            if(needF[ch] == 0)
                continue;
            
            hasF[ch]++;
            if(hasF[ch] <= needF[ch])
            {
                count++;
            }
                if(count == T.length())
                {
                    while(needF[S.charAt(s)] == 0 || 
                            hasF[S.charAt(s)] > needF[S.charAt(s)])
                    {
                        if(hasF[S.charAt(s)] > needF[S.charAt(s)])
                            hasF[S.charAt(s)]--;                            
                        s++;
                    }

                    
                    if(e-s < min)
                    {
                        min = e - s;
                        res = S.substring(s, e+1);
                    }
                }
        }
        return res;
    }
}
